package _0_5_编辑距离

/**
原题链接:
https://leetcode.cn/problems/distinct-subsequences/

115. 不同的子序列
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag

*/

func numDistinct(s string, t string) int {

	m := len(s)
	n := len(t)

	dp := make([][]int, m+1) //dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, n+1)
	}

	// 初始化
	for i := 0; i < m+1; i++ {
		dp[i][0] = 1 //如果目标字符串为空, 那么字符串1每个位置作为终点, 都有一种方案能够凑出空串
	}

	// dp[0][j] 为 0，默认值，因此不需要初始化
	for i := 1; i < m+1; i++ {
		for j := 1; j < n+1; j++ {
			if s[i-1] == t[j-1] {
				dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
			} else {
				dp[i][j] = dp[i-1][j]
			}
		}
	}
	return dp[m-1][n-1]
}
